package algorithms;

import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;

import structure.interfaces.INode;
import java.util.Random;

import algorithms.Selection.SelectionFactory.SelectionMode;
import base.Chromosome;
import base.Population;

public class GPAlgorithm {

	// chromosomes population
	private Population _pop;
	
	// the training data
	private List<Entry<Double,Double>> _trainingData;
	
	// selection mode that is used to select chromosome from the population
	private SelectionMode _selectionMode; 

	/**
	 * initialization
	 * 
	 * @param data - list of training data entries 
	 * @param mode - selection mode
	 */
	public GPAlgorithm(List<Entry<Double,Double>> data, SelectionMode mode)
	{  
		_trainingData = data;
		_selectionMode = mode;

		// init population (10 * max population size)
		_pop = new Population(10*CONST.MAX_POPULATION_SIZE);
		for (int i=0; i<10*CONST.MAX_POPULATION_SIZE; i++)
		{
			Chromosome ch = new Chromosome();
			ch.Init();
			SetFitness(ch);
			_pop.AddChromosome(ch);
		}

	}

	/**
	 * run the GP algorithm
	 */
	public void Run()
	{
		long start = System.currentTimeMillis();
		long current = start;
		
		// run for a minute
		//int genNum = 1;
		while (current - start < 60000) {
			// calculate next generation
			NextGeneration();
			//genNum++;
			current = System.currentTimeMillis();
		}
		
		/*
		System.out.println("generations: " + genNum);
		System.out.println("deep: " +  _pop.GetBestChromosome().GetDeep());
		System.out.println("fitness: " + _pop.GetBestChromosome().get_fitness());
		*/
		
		//System.out.println(genNum + "," + _pop.GetBestChromosome().GetDeep() + "," + _pop.GetBestChromosome().get_fitness() + "," + _pop.GetBestChromosome().toString());
	}

	/**
	 *  calculate the next generation
	 */
	private void NextGeneration()
	{
		// initialize selection
		Selection selectionStrategy = Selection.SelectionFactory.CreateSelection(_selectionMode, _pop);

		// initialize new population
		Population newPopulation = new Population(CONST.MAX_POPULATION_SIZE);

		// calculate number of chromosomes to copy from currnet population to the new population
		int numParents = (int)(CONST.MAX_POPULATION_SIZE * CONST.TOP_POPULATION_PRECENT_FOR_COPY);
		if (numParents%2 != 0) numParents++;
		
		// until population size is reached
		while (newPopulation.Size() < CONST.MAX_POPULATION_SIZE - numParents) {
		
			// perform cross over - for 2 selected chromosomes from current population
			Chromosome c1 = selectionStrategy.Select();
			Chromosome c2 = selectionStrategy.Select();   
			Chromosome[] childs = CrossOver(c1, c2);
			if (childs == null) continue;

			// perform mutation on the new child chromosomes
			Mutation(childs[0]);
			Mutation(childs[1]);

			// update fitness for the new child chromosomes
			SetFitness(childs[0]);
			SetFitness(childs[1]);
			
			// add the new children to new population
			newPopulation.AddChromosome(childs[0]);
			newPopulation.AddChromosome(childs[1]); 
		}

		// copy the best chromosome from the current population to the new population
		ArrayList<Chromosome> bestParents = _pop.GetTopsChromosomes(numParents);
		newPopulation.Union(bestParents);
		
		// update the population with the new created population
		_pop.SetChromosomesList(newPopulation.get_pop());

		// debugging
		//System.out.println(_pop.GetBestChromosome().get_fitness());
		//System.out.println(_pop.GetBestChromosome().get_fitness() + "," + _pop.GetAvgFitness());
	}
	
	/**
	 * Perform cross over - create 2 new chromosomes from the given chromosomes by randomly
	 * replacing subtree of each of the given chromosomes
	 * 
	 * @param c1 parent chromosome 1
	 * @param c2 parent chromosome 2
	 * @return array of 2 chromosome that are result of the cross-over, otherwise - null
	 */
	private Chromosome[] CrossOver(Chromosome c1, Chromosome c2)
	{ 		
		
		Chromosome child1 = null;
		Chromosome child2 = null;
		
		// perform cross-over with some probability
		if ((c1.GetDeep() > 1  || c2.GetDeep() > 1) && new Random().nextDouble() <= CONST.CROSSOVER_PERCENT)  {
			
			// get random subtree for cross-over for each given chromosome
			INode cross1 = c1.getRandomNode();
			INode cross2 = c2.getRandomNode();
			
			// perform cross-opver by cloning given chromosome and replacing the selected subtrees
			child1 = c1.clone(cross1, cross2);
			child2 = c2.clone(cross2, cross1);
		}
		else { // do nothing
			return null;
		}
		
		// return the new created chromosome, i.e., result of cross-over 
		return new Chromosome[] { child1, child2 };
	}

	/**
	 * Mutation function initiates mutation on the given chromosome.
	 *  
	 * @param ch - chromosome for mutations
	 */
	private void Mutation(Chromosome ch)
	{
		// generate mutation with some probability
		if (new Random().nextDouble() <= CONST.MUTATE_PERCENT) 
		{
			Mutation(ch.get_root());
		}
	}

	/**
	 * Mutation function loop through all chromosome's nodes and with CONST.MUTATE_PERCENT probability
	 * perform mutation on each node.
	 *  
	 * @param node - node for mutation
	 */
	private boolean Mutation(INode node)
	{

		if (node != null)
		{
			// generate mutation on each node with some probability
			if (new Random().nextDouble() <= CONST.MUTATE_NODE_PERCENT) 
			{
				// generate mutation
				node.generateSubTree(CONST.MAX_DEEP_MUTATION);
				return true;
			}
			else
			{
				// loop children and perform mutation
				INode[] childs = node.getChildrens();
				if (childs != null)
				{
					for (INode iNode : childs) {
						if (Mutation(iNode))
						{
							continue;
						}
					}
				}
				
			}

		}
		
		return false;
	}

	/**
	 * Returns the solution of the algorithms - the best found chromosome
	 * @return
	 */
	public Chromosome GetSolution()
	{
		return _pop.GetBestChromosome();
	}

	/**
	 * Calculate the fitness of the given chromosome - measure of the error tested on training data
	 * @param ch - the chromosome
	 * @return - the value representing the fitness
	 */
	public double CalculateFitness(Chromosome ch)
	{
		// sum total absolute difference of the chromosome equation on each entry in the training data 
		double totDiff = 0;
		for (int i = 0; i < _trainingData.size(); i++) {
			Entry<Double, Double> entry = _trainingData.get(i);
			double diff = ch.GetValue(entry.getKey()) - entry.getValue();
			totDiff += Math.abs(diff);
		}
		
		// calculate the average diff
		double fitness = totDiff/_trainingData.size();
		
		// penalty on deep of the chromosome
		int deep = ch.GetDeep();
		if (deep > CONST.MAX_DEEP_CHROMOSOME)
			fitness += fitness*0.1*deep;
		
		return fitness;
	}

	/**
	 * Set the fitness of the given chromosome
	 * @param ch
	 */
	private void SetFitness(Chromosome ch)
	{
		ch.set_fitness(CalculateFitness(ch));
	}
}